package leetcode.hot100;

import java.util.*;

@SuppressWarnings("all")
public class _39_组合总和 {

    // candidates = [2,3,6,7], target = 7, 所求解集为：[7],[2,2,3]
    // candidates = [2,3,5], target = 8, 所求解集为： [2,2,2,2],[2,3,3],[3,5]
    // 说明:candidates 中的数字可以无限制重复被选取

    private int[] candidates;
    private List<List<Integer>> res;
    private Deque<Integer> path;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.res = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return res;
        }
        this.candidates = candidates;
        this.path = new ArrayDeque<>();
        dfs(0, target);
        return res;
    }

    /**
     * @param level  搜索起点
     * @param target 每减去一个元素，目标值变小
     */
    private void dfs(int level, int target) {
        // target 为负数和 0 的时候不再产生新的孩子结点
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 重点理解这里从 level 开始搜索的语意，搜索第level层第i个数gt
        for (int i = level; i < candidates.length; i++) {
            path.addLast(candidates[i]);
            // 注意：由于每一个元素可以重复使用，下一轮搜索的起点依然是 i，这里非常容易弄错
            dfs(i, target - candidates[i]);
            // 状态重置
            path.removeLast();
        }
    }
}
